package com.github.zyflzz.cbca.java_implement;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * <h2>Cell-Based Containment Algorithm</h2>
 * 俗称网格法，Zalik 和 Kolingerova 两位大佬于 2001 年提出<sup><a href="https://www.sciencedirect.com/science/article/pii/S0098300401000371">[1]</a></sup>。
 * <p>
 * 这里借鉴了论文中的部分方法，并做了一定的修改包括：
 * <ol>
 *     <li>
 *         对于边界网格的确定，原文采用 Zalik 自己于 1997 年提出的 Code-based 算法，
 *         但是实现起来有点复杂。这里通过计算 X 和 Y 两个方向的网格交点，
 *         再进行一次单轮归并，得到有序且不重复的网格单元，效率还不错。
 *     </li>
 *     <li>
 *         对于内容的填充，原文采用 flood-fill 算法，存在大量数据效率不足问题。
 *         这里基于边界代数法进行开发，并维护了若干个适用于栅格化多边形的数据结构，效率还不错
 *     </li>
 * </ol>
 * 相关概念解释
 * <ul>
 *     <li>
 *         <b>网格</b>，即对输入的多边形数组进行处理后，得到的能够容纳整个多边形的一个网格结构；<p>
 *         以网格左下角的点为原点，向右作 X 轴，向上作 Y 轴，可以得到新的坐标系，网格结构为 {@link #net}；<p>
 *         网格的每一小格称为<b>单元</b>，单元结构定义在 {@link Cell} 中
 *     </li>
 *     <li>
 *         <b>原坐标</b>，即真实的地理或位置坐标，输入的坐标都为原坐标，类型为 double；<p>
 *         <b>格坐标</b>，即确定了网格后，在新的坐标系下的坐标，类型为 double，这种转化称为<b>网格化</b>，算法在内部处理时，均使用格坐标和单元坐标；<p>
 *         <b>单元坐标</b>，每个单元的左下角在新的坐标系中的位置，这种坐标转化称为<b>单元化</b>，就是这个单元的单元位置，从 (0,0) 开始，类型为 int；<p>
 *         <b>栅格化</b>，把多边形的每个坐标转化为格坐标，放入网格中，这个过程为栅格化
 *     </li>
 *     <li>
 *         <b>边界单元</b>，多边形栅格化后，其边对应的单元就是边界单元，边界单元结构定义在 {@link EdgeCell}；<p>
 *         <b>边界列表</b>，边界单元连成的有序无重列表，即为边界列表，边界列表结构定义在 {@link EdgeCellList}；<p>
 *         <b>边界方法</b>，用于操作一条边的方法，即为边界方法，边界方法接口定义在 {@link EdgeFunction}
 *     </li>
 * </ul>
 * 参考文献如下
 * <div>
 *     <p>
 *         [1] ZALIK B., KOLINGEROVA I.. A cell-based point-in-polygon algorithm suitable for large sets of points[J]. Computers & geosciences,2001,27(10):1135-1145. [doi: 10.1016/S0098-3004(01)00037-1]
 *     </p>
 * </div>
 *
 * @author 周逸凡 (Zhou Yifan)
 */
public class CBCA {

    /**
     * 多边形数组，坐标为原坐标
     */
    private final double[][] polygon;

    /**
     * 多边形顶点个数
     */
    private final int n;

    /**
     * 网格，长为 {@link #numOfCellX}，宽为 {@link #numOfCellY}。
     * 访问时，使用 <code>net[x][y]</code>，其中 (x,y) 表示单元坐标
     */
    private Cell[][] net;

    /**
     * 多边形数组在网格中的表示，坐标为格坐标，格坐标的表示方法为：
     * <p>
     * <code>
     * polygonInNet[i][0] = ((polygon[i][0] - xMin) / rangeX) * (numOfCellX - 1);<p>
     * polygonInNet[i][1] = ((polygon[i][1] - yMin) / rangeY) * (numOfCellY - 1);
     * </code>
     */
    private final double[][] polygonInNet;

    /**
     * 边界列表
     */
    private final EdgeCellList edgeCellList;

    /**
     * 初始化用时，单位：毫秒
     */
    private final long initTime;

    /* 基本信息部分 */

    /**
     * 网格密度，范围为在 [2,1000]，超出范围的默认修正为 2
     */
    private final double density;
    /**
     * 多边形中 x 坐标的最大值（原坐标）
     */
    private double xMax;
    /**
     * 多边形中 x 坐标的最小值（原坐标）
     */
    private double xMin;
    /**
     * 多边形中 y 坐标的最大值（原坐标）
     */
    private double yMax;
    /**
     * 多边形中 y 坐标的最小值（原坐标）
     */
    private double yMin;
    /**
     * 网格的宽长比，<code>ratio = (yMax - yMin) / (xMax - xMin);</code>
     */
    private double ratio;
    /**
     * X 方向上单元的个数，<code>numOfCellX = (int) Math.ceil(density * ratio * Math.sqrt(n));</code>
     */
    private int numOfCellX;
    /**
     * Y 方向上单元的个数，<code>numOfCellY = (int) Math.ceil(density * Math.sqrt(n) / ratio);</code>
     */
    private int numOfCellY;
    /**
     * 单个 cell 的 X 测距大小，<code>sizeOfCellX = (xMax - xMin) / numOfCellX;</code>
     */
    private double sizeOfCellX;
    /**
     * 单个 cell 的 Y 测距大小，<code>sizeOfCellY = (yMax - yMin) / numOfCellY;</code>
     */
    private double sizeOfCellY;

    /**
     * 经测试，按如下公式计算出的时间复杂度为 O(n)=10<sup>6</sup> 时，实际耗时约 300-400ms
     *
     * @param polygon 多边形数组，传入的数组是有序的，默认最后一个点连接第一个点
     * @param density 网格密度，范围为在 [2,1000]，超出范围的默认修正为 2。
     *                用 d 表示 density，n 表示顶点个数，算法的<b>空间复杂度</b>可用如下公式表示
     *                <p>
     *                S(n)=n·d<sup>2</sup>
     *                <p>
     *                算法的初始化<b>时间复杂度</b>可用如下公式表示
     *                <p>
     *                O(n)=n·d<sup>2</sup>
     *                <p>
     *                因此网格密度的大小设置要慎重，建议 S(n) < 4×10<sup>8</sup>，否则很容易出现 {@link StackOverflowError};
     *                建议 O(n) < 2×10<sup>8</sup>，能够保证运算时长大概率在 3s 内。
     *                若无特殊需求，一般<b>建议网格密度为 2</b>，即可保证占用尽量少的空间，且用时一般在 300ms 甚至 30ms 以内。
     *                在测试时，可以通过 {@link #getInitTime()} 获取初始化用时
     */
    public CBCA(double[][] polygon, double density) {
        long start = System.currentTimeMillis();
        this.polygon = polygon;
        if (density < 2 || density > 1000) {
            this.density = 2;
        } else {
            this.density = density;
        }
        this.n = polygon.length;
        this.polygonInNet = new double[n][2];
        this.edgeCellList = new EdgeCellList(n);
        calcBaseInfo();
        rasterize();
        long end = System.currentTimeMillis();
        this.initTime = end - start;
    }

    /* 初始化部分的核心性方法 */

    /**
     * 计算一些基本信息，包括：
     * <table>
     *     <tr><th>变量名</th><th>含义</th></tr>
     *     <tr><td>{@link #xMax}</td><td>多边形中 x 坐标的最大值（原始位置）</td></tr>
     *     <tr><td>{@link #xMin}</td><td>多边形中 x 坐标的最小值（原始位置）</td></tr>
     *     <tr><td>{@link #yMax}</td><td>多边形中 y 坐标的最大值（原始位置）</td></tr>
     *     <tr><td>{@link #yMin}</td><td>多边形中 y 坐标的最小值（原始位置）</td></tr>
     *     <tr><td>{@link #ratio}</td><td>宽长比</td></tr>
     *     <tr><td>{@link #numOfCellX}</td><td>X 方向上 cell 个数</td></tr>
     *     <tr><td>{@link #numOfCellY}</td><td>Y 方向上 cell 个数</td></tr>
     *     <tr><td>{@link #sizeOfCellX}</td><td>单个 cell 的 X 测距大小</td></tr>
     *     <tr><td>{@link #sizeOfCellY}</td><td>单个 cell 的 Y 测距大小</td></tr>
     *     <tr><td>{@link #net}</td><td>cell 网格</td></tr>
     *     <tr><td>{@link #polygonInNet}</td><td>多边形数组在 net 中的坐标</td></tr>
     * </table>
     */
    private void calcBaseInfo() {
        xMax = findxMax(0, n - 1);
        xMin = findxMin(0, n - 1);
        yMax = findyMax(0, n - 1);
        yMin = findyMin(0, n - 1);
        double rangeX = xMax - xMin;
        double rangeY = yMax - yMin;
        // 网格信息部分
        ratio = rangeX / rangeY;
        numOfCellX = (int) Math.ceil(density * ratio * Math.sqrt(n));
        numOfCellY = (int) Math.ceil(density * Math.sqrt(n) / ratio);
        sizeOfCellX = rangeX / numOfCellX;
        sizeOfCellY = rangeY / numOfCellY;
        // 初始化 net
        net = new Cell[numOfCellX][numOfCellY];
        for (int x = 0; x < numOfCellX; x++) {
            for (int y = 0; y < numOfCellY; y++) {
                net[x][y] = new Cell(x, y);
            }
        }
        // 计算多边形数组在网格中的表示
        // 坐标范围：0 <= x < numOfCellX, 0 <= y < numOfCellY
        IntStream.range(0, n).forEach(i -> {
            polygonInNet[i][0] = ((polygon[i][0] - xMin) / rangeX) * (numOfCellX - 1);
            polygonInNet[i][1] = ((polygon[i][1] - yMin) / rangeY) * (numOfCellY - 1);
        });
    }

    /**
     * 栅格化，进行两轮扫描
     * <ol>
     *     <li>第一轮扫描：边界扫描，初始化边数组，这一步时间复杂度约为 O(n)=d<sup>2</sup>·n<sup>1/2</sup></li>
     *     <li>第二轮扫描：网格代数化，这一步时间复杂度为 O(n)=d<sup>2</sup>·n</li>
     * </ol>
     */
    private void rasterize() {
        scanEdge();
        algebraNet();
    }

    /**
     * 边界扫描，属于第一轮扫描，该操作与其他初始化操作互斥
     */
    private synchronized void scanEdge() {
        IntStream.range(0, n).forEach(i -> scanOneEdge(
                polygonInNet[i][0], polygonInNet[i][1],
                polygonInNet[(i + 1) % n][0], polygonInNet[(i + 1) % n][1])
        );
    }

    /**
     * 网格代数化，使用边界代数法，属于第二轮扫描，该操作与其他初始化操作互斥
     */
    private synchronized void algebraNet() {
        edgeCellList.execFunctionOneTurn(this::algebraOneEdge);
    }

    /**
     * 扫描多边形的一条边，确定哪些网格单元是边界点。属于第一轮扫描的子操作
     *
     * @param xStart 起点 X 坐标（格坐标）
     * @param yStart 起点 Y 坐标（格坐标）
     * @param xEnd   终点 X 坐标（格坐标）
     * @param yEnd   终点 Y 坐标（格坐标）
     */
    private synchronized void scanOneEdge(double xStart, double yStart, double xEnd, double yEnd) {
        // 计算有向跨度
        double vecrX = xEnd - xStart, vecrY = yEnd - yStart;
        if (vecrX == 0 && vecrY == 0) return;
        Edge edge = new Edge(xStart, yStart, xEnd, yEnd);
        // 计算单元坐标
        int cxStart = (int) Math.floor(xStart), cyStart = (int) Math.floor(yStart);
        int cxEnd = (int) Math.floor(xEnd), cyEnd = (int) Math.floor(yEnd);
        int x = cxStart, y = cyStart;
        // 考虑多种情况，目的是为了简化运算，需要注意扫描一定要保证从 Start 到 End 的方向
        if (cxStart == cxEnd) {
            // 同一列网格中的直线，需要保证首尾有序，不可并行
            if (cyStart < cyEnd) for (y = cyStart; y <= cyEnd; y++) makeEdgeCell(x, y, edge);
            else for (y = cyStart; y >= cyEnd; y--) makeEdgeCell(x, y, edge);
        } else if (cyStart == cyEnd) {
            // 同一行网格中的直线，需要保证首尾有序，不可并行
            if (cxStart < cxEnd) for (x = cxStart; x <= cxEnd; x++) makeEdgeCell(x, y, edge);
            else for (x = cxStart; x >= cxEnd; x--) makeEdgeCell(x, y, edge);
        } else {
            // 一般直线
            double k = (yEnd - yStart) / (xEnd - xStart);
            double b = yStart - k * xStart;
            scanObliqueEdge(k, b, cxStart, cyStart, cxEnd, cyEnd, edge);
        }
    }

    /**
     * 扫描斜边
     *
     * @param k       斜率
     * @param b       纵截距
     * @param cxStart 起点 X 坐标（单元坐标）
     * @param cyStart 起点 Y 坐标（单元坐标）
     * @param cxEnd   终点 X 坐标（单元坐标）
     * @param cyEnd   终点 Y 坐标（单元坐标）
     */
    private void scanObliqueEdge(double k, double b, int cxStart, int cyStart, int cxEnd, int cyEnd, Edge edge) {
        // 先获取 X Y 方向上的扫描结果
        int[][] xEdges = scanObliqueEdgeX(k, b, cxStart, cxEnd);
        int[][] yEdges = scanObliqueEdgeY(k, b, cyStart, cyEnd);
        int xEdgesLen = xEdges.length, yEdgesLen = yEdges.length;
        // 计算距离数组（为了简便，无需开方），用于排序
        int len = xEdgesLen + yEdgesLen;
        double[] distance = new double[len];
        IntStream.range(0, xEdgesLen).forEach(i ->
                distance[i] = (xEdges[i][0] - cxStart) * (xEdges[i][0] - cxStart)
                        + (xEdges[i][1] - cyStart) * (xEdges[i][1] - cyStart));
        IntStream.range(0, yEdgesLen).forEach(i ->
                distance[i + xEdgesLen] = (yEdges[i][0] - cxStart) * (yEdges[i][0] - cxStart)
                        + (yEdges[i][1] - cyStart) * (yEdges[i][1] - cyStart));
        // 根据距离数组进行排序，由于 X 数组本身有序，Y 数组本身有序，因此可以简化
        // 在排序时，我们仅仅关注游标位置，而无需特别关注距离值的具体值，可以理解为单次归并
        int i = 0, j = xEdgesLen;
        List<int[]> edges = new ArrayList<>();
        edges.add(new int[]{cxStart, cyStart});
        while (i < xEdgesLen && j < len) {
            if (distance[i] < distance[j]) {
                if (i == 0 || !doubleEquals(distance[i], distance[i - 1])) edges.add(xEdges[i]);
                i++;
                continue;
            }
            if (distance[i] > distance[j]) {
                if (j == xEdgesLen || !doubleEquals(distance[j], distance[j - 1])) edges.add(yEdges[j - xEdgesLen]);
                j++;
                continue;
            }
            // 这种情况一般不会发生，如果发生了，一般是精度导致
            if (doubleEquals(distance[i], distance[j])) {
                edges.add(xEdges[i]);
                i++;
                j++;
            }
        }
        edges.add(new int[]{cxEnd, cyEnd});
        edges.forEach(e -> makeEdgeCell(e[0], e[1], edge));
    }

    /**
     * 扫描 X 方向上的边
     *
     * @param k       斜率
     * @param b       纵截距
     * @param cxStart 起点 X 坐标（单元坐标）
     * @param cxEnd   终点 X 坐标（单元坐标）
     */
    private int[][] scanObliqueEdgeX(double k, double b, int cxStart, int cxEnd) {
        int length = Math.abs(cxEnd - cxStart);
        int[][] res = new int[length][];
        IntStream.range(0, length).forEach(cxStart < cxEnd
                ? (i -> res[i] = new int[]{cxStart + 1 + i, (int) Math.floor(k * (cxStart + 1 + i) + b)}) // X 递增
                : (i -> res[i] = new int[]{cxStart - i, (int) Math.floor(k * (cxStart - i) + b)})); // X 递减
        return res;
    }

    /**
     * 扫描 Y 方向上的边
     *
     * @param k       斜率
     * @param b       纵截距
     * @param cyStart 起点 Y 坐标（单元坐标）
     * @param cyEnd   终点 Y 坐标（单元坐标）
     */
    private int[][] scanObliqueEdgeY(double k, double b, int cyStart, int cyEnd) {
        int length = Math.abs(cyEnd - cyStart);
        int[][] res = new int[length][];
        IntStream.range(0, length).forEach(k > 0 ?
                cyStart < cyEnd ?
                        (i -> res[i] = new int[]{(int) Math.floor((cyStart + 1 + i - b) / k), (cyStart + 1 + i)}) :
                        (i -> res[i] = new int[]{(int) Math.floor((cyStart - i - b) / k), (cyStart - i)}) :
                cyStart < cyEnd ?
                        (i -> res[i] = new int[]{(int) Math.floor((cyStart + i - b) / k), (cyStart + i)}) :
                        (i -> res[i] = new int[]{(int) Math.floor((cyStart - 1 - i - b) / k), (cyStart - 1 - i)}));
        return res;
    }

    /**
     * 构建边界单元
     *
     * @param x    X 坐标
     * @param y    Y 坐标
     * @param edge 经过该单元的边
     */
    private void makeEdgeCell(int x, int y, Edge edge) {
        if (net[x][y].isEdge) {
            //  如果已经是边界单元了，那么就添加新边
            ((EdgeCell) net[x][y]).addEdge(edge);
        } else {
            net[x][y] = new EdgeCell(net[x][y], edge);
            edgeCellList.add((EdgeCell) net[x][y]);
        }
    }

    /**
     * 边界代数填充
     *
     * @param cxStart 起点 X 坐标（单元坐标）
     * @param cyStart 起点 Y 坐标（单元坐标）
     * @param cxEnd   终点 X 坐标（单元坐标）
     * @param cyEnd   终点 Y 坐标（单元坐标）
     */
    private void algebraOneEdge(int cxStart, int cyStart, int cxEnd, int cyEnd) {
        // 首先检查是否是水平线，如果是水平线就跳过
        if (cyStart == cyEnd) return;
        // 计算纵向跨度
        int length = Math.abs(cyEnd - cyStart);
        // 其次检查是否是垂线，如果是垂线，那么简化操作
        if (cxStart == cxEnd) {
            // 可实现并行流操作，因为确定上下行、起止点后，填充顺序无关紧要
            IntStream.range(0, length)
                    .forEach(cyStart < cyEnd ?
                            (i -> up(cxStart, cyStart + i))
                            : (i -> dw(cxStart, cyEnd + i)));
        } else {
            // 斜线的逻辑是：从 Start 到 End，按中间纵向走过的网格数来进行上下行，而方程仅用于确定中间的坐标
            double m = (double) (cxEnd - cxStart) / (cyEnd - cyStart);
            double c = cxStart - m * cyStart;
            // 可实现并行流操作，因为确定上下行、起止点后，填充顺序无关紧要
            IntStream.range(0, length)
                    .forEach(cyStart < cyEnd ?
                            (i -> up((int) Math.floor(m * (cyStart + i) + c), (cyStart + i)))
                            : (i -> dw((int) Math.floor(m * (cyEnd + i) + c), (cyEnd + i))));
        }
    }

    /**
     * 上行，方向向量左侧 + 1
     *
     * @param x 基准 X 坐标（单元坐标）
     * @param y 基准 Y 坐标（单元坐标）
     */
    private void up(int x, int y) {
        IntStream.range(0, x).forEach(i -> net[i][y].tup());
    }

    /**
     * 下行，方向向量右侧 - 1
     *
     * @param x 基准 X 坐标（单元坐标）
     * @param y 基准 Y 坐标（单元坐标）
     */
    private void dw(int x, int y) {
        IntStream.range(0, x).forEach(i -> net[i][y].tdw());
    }

    /* 计算部分的核心性方法 */

    /**
     * 点相对于多边形的位置，有内部（对应 0）、外部（对应 1）、边三种位置类型
     */
    public enum Position {
        INNER, OUTER, EDGE;

        public static Position parsePosition(byte cellType) {
            switch (cellType) {
                case 0:
                    return OUTER;
                case 1:
                    return INNER;
                default:
                    return EDGE;
            }
        }

        public static Position parseOppositePosition(byte cellType) {
            switch (cellType) {
                case 0:
                    return INNER;
                case 1:
                    return OUTER;
                default:
                    return EDGE;
            }
        }
    }

    /**
     * 处理结果，包含如下信息
     * <table>
     *     <tr><th>名称</th><th>含义</th></tr>
     *     <tr><td>{@link #point}</td><td>输入的真实坐标</td></tr>
     *     <tr><td>{@link #pointNormalized}</td><td>真实坐标转化后的格坐标</td></tr>
     *     <tr><td>{@link #pointCellized}</td><td>格坐标向下取整后的单元坐标</td></tr>
     *     <tr><td>{@link #cellType}</td><td>对应单元的类型（内是 0，外是 1）</td></tr>
     *     <tr><td>{@link #position}</td><td>真实坐标相对于多边形的位置（内、外、边）</td></tr>
     *     <tr><td>{@link #judgeTime}</td><td>判定过程所用的总时间</td></tr>
     *     <tr><td>{@link #calcTime}</td><td>除去一些信息封装操作，纯计算时间</td></tr>
     *     <tr><td>{@link #edge}</td><td>如果当前坐标在边上，那么是哪一条边</td></tr>
     *     <tr><td>{@link #message}</td><td>其他信息</td></tr>
     * </table>
     */
    public static final class Result {
        private double[] point;
        private double[] pointNormalized;
        private int[] pointCellized;
        private byte cellType;
        private Position position;
        private long judgeTime;
        private long calcTime;
        private Edge edge;
        private String message = "OK";

        public double[] getPoint() {
            return point;
        }

        public double[] getPointNormalized() {
            return pointNormalized;
        }

        public int[] getPointCellized() {
            return pointCellized;
        }

        public byte getCellType() {
            return cellType;
        }

        public Position getPosition() {
            return position;
        }

        public long getJudgeTime() {
            return judgeTime;
        }

        public long getCalcTime() {
            return calcTime;
        }

        public Edge getEdge() {
            return edge;
        }

        public String getMessage() {
            return message;
        }

        @Override
        public String toString() {
            return "Result{\n" +
                    "\tpoint = (" + point[0] + "," + point[1] + ")" +
                    ",\n\tpointNormalized = (" + pointNormalized[0] + "," + pointNormalized[1] + ")" +
                    ",\n\tpointCellized = (" + pointCellized[0] + "," + pointCellized[1] + ")" +
                    ",\n\tcellType = " + cellType +
                    ",\n\tposition = " + position +
                    ",\n\tjudgeTime = " + judgeTime + "ms" +
                    ",\n\tcalcTime = " + calcTime + "ms" +
                    ",\n\tedge = " + edge +
                    ",\n\tmessage = " + message +
                    "\n}";
        }
    }

    /**
     * 判断目标点的位置，最好情况为 O(1)，最坏情况为 O(d<sup>2</sup>·n<sup>1/2</sup>)
     *
     * @param x X 坐标（真实坐标）
     * @param y Y 坐标（真实坐标）
     * @return {@link Result}，一系列处理信息，可以通过 {@link Result#getPosition()} 获取判定的位置
     */
    public Result judgePosition(double x, double y) {
        Result result = new Result();
        // 开始计时
        long start = System.currentTimeMillis();
        result.point = new double[]{x, y};
        // 将点标准化
        double nx = rasterizeX(x), ny = rasterizeY(y);
        result.pointNormalized = new double[]{nx, ny};
        // 将点单元化
        int cx = (int) Math.floor(nx), cy = (int) Math.floor(ny);
        result.pointCellized = new int[]{cx, cy};
        // 如果超出了范围，那么必定是在外面
        if (x < xMin || x > xMax || y < yMin || y > yMax) {
            result.cellType = 0;
            result.position = Position.OUTER;
            result.message = "目标点超出网格之外，即在目标多边形之外";
        } else {
            // 获取对应点的类型
            byte type = net[cx][cy].type;
            result.cellType = type;
            // 判断是否是边界单元
            if (net[cx][cy].isEdge) {
                // 如果是边界单元，需要进一步判断
                judgePositionInEdgeCell(result);
            } else {
                // 如果不是边界单元，那么即可快速判断
                result.position = Position.parsePosition(type);
                result.message = "目标点在网格之内，且不是边界单元，可直接判断内外";
            }
        }
        // 结束计时
        long end = System.currentTimeMillis();
        result.judgeTime = end - start;
        return result;
    }

    /**
     * 输入的坐标位于边界单元，进行进一步判断
     *
     * @param result 未处理完毕的 Result
     */
    private void judgePositionInEdgeCell(Result result) {
        // 开始计时
        long start = System.currentTimeMillis();
        // 从未处理完毕的 result 中获取一些信息
        double x = result.point[0], y = result.point[1];
        int cx = result.pointCellized[0], cy = result.pointCellized[1];
        // 获取边界单元信息
        EdgeCell edgeCell = (EdgeCell) net[cx][cy];
        Edge[] edges = edgeCell.edges;
        // 遍历边界单元的所有边
        int crossCount = 0;
        for (Edge edge : edges) {
            if (edge.onEdge(x, y)) {
                // 如果恰好在边上
                result.position = Position.EDGE;
                result.edge = edge;
                result.message = "目标点恰好在边上，所在边为 " + edge;
                break;
            } else {
                // 计算叉积，判断是否有交点
                if (isIntersect(cx, cy, x, y, edge.xStart, edge.yStart, edge.xEnd, edge.yEnd)) {
                    crossCount++;
                }
            }
        }
        if (result.position != Position.EDGE) {
            // 如果交点个数为偶数，那么同内外，否则属性相反
            result.position = crossCount % 2 == 0
                    ? Position.parsePosition(result.cellType)
                    : Position.parseOppositePosition(result.cellType);
            result.message = "目标点与所在单元内左下角的连线，跟所在单元内的所有边的交点个数为 " + crossCount + "，左下角的点类型为 " + result.cellType;
        }
        long end = System.currentTimeMillis();
        result.calcTime = end - start;
    }

    private boolean isIntersect(
            double xStartA, double yStartA, double xEndA, double yEndA,
            double xStartB, double yStartB, double xEndB, double yEndB
    ) {
        if (Math.max(xStartA, xEndA) < Math.min(xStartB, xEndB)
                || Math.max(yStartA, yEndA) < Math.min(yStartB, yEndB)
                || Math.min(xStartA, xEndA) > Math.max(xStartB, xEndB)
                || Math.min(yStartA, yEndA) > Math.max(yStartB, yEndB)
        ) return false;
        double c1 = crossProduct(xStartA, yStartA, xEndA, yEndA, xStartB, yStartB);
        double c2 = crossProduct(xEndA, yEndA, xStartB, yStartB, xEndB, yEndB);
        double c3 = crossProduct(xStartB, yStartB, xEndB, yEndB, xStartA, yStartA);
        double c4 = crossProduct(xEndB, yEndB, xStartA, yStartA, xEndA, yEndA);
        return !(c2 * c4 > 0 || c1 * c3 > 0);
    }

    private double crossProduct(double baseX, double baseY, double xa, double ya, double xb, double yb) {
        return ((baseX - xa) * (baseY - yb) - (baseX - xb) * (baseY - ya));
    }

    /**
     * @param x 真实的 X 坐标
     * @return 栅格化后的 X 坐标
     */
    public double rasterizeX(double x) {
        return ((x - xMin) / (xMax - xMin)) * (numOfCellX - 1);
    }

    /**
     * @param y 真实的 Y 坐标
     * @return 栅格化后的 Y 坐标
     */
    public double rasterizeY(double y) {
        return ((y - yMin) / (yMax - yMin)) * (numOfCellY - 1);
    }

    /**
     * @param x 实际 X 坐标
     * @return 单元化后的 X 坐标
     */
    public int cellizeX(double x) {
        return (int) Math.floor(((x - xMin) / (xMax - xMin)) * (numOfCellX - 1));
    }

    /**
     * @param y 实际 Y 坐标
     * @return 单元化后的 Y 坐标
     */
    public int cellizeY(double y) {
        return (int) Math.floor(((y - yMin) / yMax - yMin) * (numOfCellY - 1));
    }

    /* 工具性方法，以及部分 getter/setter 方法 */

    private static boolean doubleEquals(double a, double b) {
        return Math.abs(a - b) < PRECISION;
    }

    private double findxMax(int left, int right) {
        if (left == right) return polygon[left][0];
        int mid = left + (right - left) / 2;
        double leftMax = findxMax(left, mid);
        double rightMax = findxMax(mid + 1, right);
        return Math.max(leftMax, rightMax);
    }

    private double findxMin(int left, int right) {
        if (left == right) return polygon[left][0];
        int mid = left + (right - left) / 2;
        double leftMax = findxMin(left, mid);
        double rightMax = findxMin(mid + 1, right);
        return Math.min(leftMax, rightMax);
    }

    private double findyMax(int left, int right) {
        if (left == right) return polygon[left][1];
        int mid = left + (right - left) / 2;
        double leftMax = findyMax(left, mid);
        double rightMax = findyMax(mid + 1, right);
        return Math.max(leftMax, rightMax);
    }

    private double findyMin(int left, int right) {
        if (left == right) return polygon[left][1];
        int mid = left + (right - left) / 2;
        double leftMax = findyMin(left, mid);
        double rightMax = findyMin(mid + 1, right);
        return Math.min(leftMax, rightMax);
    }

    public int getN() {
        return n;
    }

    public double[][] getPolygon() {
        return polygon;
    }

    public Cell[][] getNet() {
        return net;
    }

    public double[][] getPolygonInNet() {
        return polygonInNet;
    }

    public EdgeCell[] getEdgeList() {
        return edgeCellList.getEdgeCells();
    }

    public long getInitTime() {
        return initTime;
    }

    public double getDensity() {
        return density;
    }

    public int getNumOfCellX() {
        return numOfCellX;
    }

    public int getNumOfCellY() {
        return numOfCellY;
    }

    public double getRatio() {
        return ratio;
    }

    public double getSizeOfCellX() {
        return sizeOfCellX;
    }

    public double getSizeOfCellY() {
        return sizeOfCellY;
    }

    public double getxMax() {
        return xMax;
    }

    public double getxMin() {
        return xMin;
    }

    public double getyMax() {
        return yMax;
    }

    public double getyMin() {
        return yMin;
    }

    public String showBaseInfo() {
        return "CBCA_BaseInfo{" +
                "\n\tn = " + n +
                "\n\tdensity = " + density +
                ",\n\tnumOfCellX = " + numOfCellX +
                ",\n\tnumOfCellY = " + numOfCellY +
                ",\n\tratio = " + ratio +
                ",\n\tsizeOfCellX = " + sizeOfCellX +
                ",\n\tsizeOfCellY = " + sizeOfCellY +
                ",\n\txMax = " + xMax +
                ",\n\txMin = " + xMin +
                ",\n\tyMax = " + yMax +
                ",\n\tyMin = " + yMin +
                "\n}";
    }

    public String showEdgeList() {
        return Arrays.stream(getEdgeList())
                .map(EdgeCell::toStringln)
                .collect(Collectors.joining());
    }

    public String showEdgeListInLine() {
        return Arrays.stream(getEdgeList())
                .map(e -> "(" + e.getX() + "," + e.getY() + "),")
                .collect(Collectors.joining());
    }

    public String showPolygon() {
        return Arrays.stream(polygon)
                .map(p -> "(" + p[0] + "," + p[1] + ")" + '\n')
                .collect(Collectors.joining());
    }

    public String showPolygonInLine() {
        return Arrays.stream(polygon)
                .map(p -> "(" + p[0] + "," + p[1] + "),")
                .collect(Collectors.joining());
    }

    public String showNet() {
        StringBuilder builder = new StringBuilder();
        int m = net[0].length;
        StringBuilder head = new StringBuilder("X/Y\t|\t");
        for (int i = 0; i < m; i++) {
            head.append(i).append("\t");
        }
        head.append("|\n");
        for (int i = 0; i < m + 2; i++) {
            head.append("----");
        }
        builder.append(head).append("|\n");
        int x = 0;
        for (Cell[] line : net) {
            builder.append(x).append("\t|\t");
            for (Cell cell : line) {
                builder.append(cell.type).append("\t");
            }
            builder.append("|\n");
            x++;
        }
        return builder.toString();
    }

    public String showEmbellishedNet() {
        StringBuilder builder = new StringBuilder();
        int m = net[0].length;
        StringBuilder head = new StringBuilder("X/Y\t|\t");
        IntStream.range(0, m).forEach(i -> head.append(i).append('\t'));
        head.append('\n');
        builder.append(head);
        int x = 0;
        for (Cell[] line : net) {
            builder.append(x).append("\t|\t");
            for (Cell cell : line) {
                builder.append(embellishCell(cell)).append('\t');
            }
            builder.append('\n');
            x++;
        }
        return builder.toString();
    }

    private char embellishCell(Cell cell) {
        if (cell.isEdge) return '@';
        else if (cell.type > 0) return '*';
        else return '-';
    }

    /* 边界列表 */

    public EdgeCellList getEdgeCellList() {
        return edgeCellList;
    }

    /**
     * 边界列表，轻量级的 List（并没有实现 List 接口），底层原理是动态数组
     * <ul>
     *     <li>基本原理是维护一个动态 EdgeCell 数组，当容量满时，若还需添加，则容量扩大为原来的 1.5 倍；</li>
     *     <li>初始容量为 {@link #n}，因为一般实际边的个数等同于顶点个数，而边界单元个数和这个也相仿；</li>
     *     <li>对于外界而言，该列表是只读的，且任何操作也只能是读操作，不可以是写操作，且不可继承</li>
     * </ul>
     */
    public static final class EdgeCellList {

        /**
         * 边界列表
         */
        private EdgeCell[] edgeCells;

        /**
         * 最大容量，可动态变化
         */
        private int maxSize;

        /**
         * 当前大小
         */
        private int currentSize = 0;

        private EdgeCellList(int initSize) {
            this.maxSize = initSize;
            this.edgeCells = new EdgeCell[maxSize];
        }

        /**
         * 添加边界点，不查重（因此如有不可重复的需求，需要在使用该方法前通过一些手段去重）
         *
         * @param edgeCell 边界单元
         */
        private void add(EdgeCell edgeCell) {
            if (currentSize >= maxSize) enlarge();
            edgeCells[currentSize] = edgeCell;
            currentSize++;
        }

        /**
         * @param index 索引
         * @return 索引处的边界点
         */
        public EdgeCell getEdgeCell(int index) {
            return edgeCells[index];
        }

        /**
         * @return 边界列表
         */
        public EdgeCell[] getEdgeCells() {
            EdgeCell[] newEdgeCells = new EdgeCell[currentSize];
            System.arraycopy(edgeCells, 0, newEdgeCells, 0, currentSize);
            return newEdgeCells;
        }

        /**
         * @return 当前列表长度
         */
        public int size() {
            return currentSize;
        }

        /**
         * @return 没有任何元素 true，非空 false
         */
        public boolean isEmpty() {
            return currentSize == 0;
        }

        /**
         * 扩容，扩张倍率是 1.5
         */
        private void enlarge() {
            // 没有到临界点无需扩容
            if (currentSize < maxSize) return;
            // 增大最大容量
            maxSize = (int) (maxSize * 1.5);
            // 数组复制
            EdgeCell[] newEdgeCells = new EdgeCell[maxSize];
            System.arraycopy(edgeCells, 0, newEdgeCells, 0, edgeCells.length);
            edgeCells = newEdgeCells;
        }

        /**
         * 执行一轮指定的操作，该操作只能是读属性操作。即使是写操作类型，由于参数传递是引用传递，也无法更改原始内容。
         *
         * @param function 指定的方法，需要实现 {@link EdgeFunction} 接口
         */
        public void execFunctionOneTurn(EdgeFunction function) {
            IntStream.range(0, currentSize).forEach(i -> function.run(
                    edgeCells[i].getX(), edgeCells[i].getY(),
                    edgeCells[(i + 1) % currentSize].getX(), edgeCells[(i + 1) % currentSize].getY()));
        }
    }

    /**
     * 边界方法，需要实现 {@link #run(int, int, int, int)} 方法。
     * 需要注意的是，在边界列表未初始化完成时，使用便操作函数无意义。
     * 该操作函数应当是读操作而非写操作。
     */
    @FunctionalInterface
    public interface EdgeFunction {
        /**
         * 对于一个边需要操作的方法
         *
         * @param cxStart 边的起点 X 坐标
         * @param cyStart 边的起点 Y 坐标
         * @param cxEnd   边的终点 X 坐标
         * @param cyEnd   边的终点 Y 坐标
         */
        void run(int cxStart, int cyStart, int cxEnd, int cyEnd);
    }

    /**
     * 单元，一个网格的基本单位，对于外界是只读的，包含以下属性
     * <table>
     *     <tr><th>属性</th><th>含义</th></tr>
     *     <tr><td>{@link #x}</td><td>单元坐标的 X 坐标</td></tr>
     *     <tr><td>{@link #y}</td><td>单元坐标的 Y 坐标</td></tr>
     *     <tr><td>{@link #type}</td><td>单元的类型（内是 0，外是 1）</td></tr>
     *     <tr><td>{@link #isEdge}</td><td>当前单元是否是边</td></tr>
     * </table>
     * 如果当前单元是边的话，那么可以转化成 {@link EdgeCell} 进行更进一步的操作
     */
    public static class Cell {
        private final int x;
        private final int y;
        private byte type;
        private final boolean isEdge;

        private Cell(int x, int y) {
            this.x = x;
            this.y = y;
            this.type = 0;
            this.isEdge = false;
        }

        private Cell(int x, int y, byte type, boolean isEdge) {
            this.x = x;
            this.y = y;
            this.type = type;
            this.isEdge = isEdge;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public byte getType() {
            return type;
        }

        public boolean isEdge() {
            return isEdge;
        }

        public boolean verifyType(byte type) {
            return this.type == type;
        }

        public boolean verifyCoordinate(int x, int y) {
            return this.x == x && this.y == y;
        }

        private void tup() {
            this.type++;
        }

        private void tdw() {
            this.type--;
        }

        @Override
        public String toString() {
            return "(" + x + "," + y + ";" + type + ")";
        }
    }

    /**
     * 边界单元，对外界是只读的，且不可继承，包含如下属性
     * <table>
     *     <tr><th>属性</th><th>含义</th></tr>
     *     <tr><td>{@link #edges}</td><td>所包含的多边形的边数组</td></tr>
     *     <tr><td>{@link #size}</td><td>所包含的多边形的边的数量</td></tr>
     * </table>
     */
    public static final class EdgeCell extends Cell {
        private Edge[] edges;
        private int size;

        private EdgeCell(Cell cell, Edge edge) {
            super(cell.x, cell.y, cell.type, true);
            this.edges = new Edge[]{edge};
            this.size = 1;
        }

        private void addEdge(Edge edge) {
            if (edge.equals(edges[size - 1])) return;
            Edge[] newEdges = new Edge[size + 1];
            System.arraycopy(edges, 0, newEdges, 0, size);
            newEdges[size] = edge;
            edges = newEdges;
            size++;
        }

        public boolean equals(int x, int y) {
            return verifyCoordinate(x, y);
        }

        public Edge[] getEdges() {
            return edges;
        }

        public int getSize() {
            return size;
        }

        @Override
        public String toString() {
            return super.toString() + "\t: " + size + " edges\t"
                    + IntStream.range(0, size)
                    .mapToObj(i -> edges[i].toString() + ",\t")
                    .collect(Collectors.joining());
        }

        public String toStringln() {
            return this + "\n";
        }
    }

    /**
     * 多边形的一条边，在边界扫描时动态创建，添加至边界单元中，对于外界是只读的
     */
    public static final class Edge {
        private final double xStart;
        private final double yStart;
        private final double xEnd;
        private final double yEnd;

        private Edge(double xStart, double yStart, double xEnd, double yEnd) {
            this.xStart = xStart;
            this.yStart = yStart;
            this.xEnd = xEnd;
            this.yEnd = yEnd;
        }

        public boolean equals(double xStart, double yStart, double xEnd, double yEnd) {
            return Math.abs(this.xStart - xStart) < PRECISION
                    && Math.abs(this.yStart - yStart) < PRECISION
                    && Math.abs(this.xEnd - xEnd) < PRECISION
                    && Math.abs(this.yEnd - yEnd) < PRECISION;
        }

        public boolean equals(Edge edge) {
            return equals(edge.xStart, edge.yStart, edge.xEnd, edge.yEnd);
        }

        public boolean onEdge(double x, double y) {
            if ((x - xStart) * (x - xEnd) < 0) return true;
            return doubleEquals((x - xStart) * (y - yEnd), (x - xEnd) * (y - yStart));
        }

        public double getxStart() {
            return xStart;
        }

        public double getyStart() {
            return yStart;
        }

        public double getxEnd() {
            return xEnd;
        }

        public double getyEnd() {
            return yEnd;
        }

        @Override
        public String toString() {
            return "(" + String.format("%.16f", xStart) + ","
                    + String.format("%.16f", yStart) + ")->("
                    + String.format("%.16f", xEnd) + ","
                    + String.format("%.16f", yEnd) + ")";
        }
    }

    /**
     * 精度
     */
    public static final double PRECISION = 1E-10;

    @Override
    public String toString() {
        return "CBCA{" +
                "polygon=" + Arrays.toString(polygon) +
                ", n=" + n +
                ", net=" + Arrays.toString(net) +
                ", polygonInNet=" + Arrays.toString(polygonInNet) +
                ", edgeCellList=" + edgeCellList +
                ", initTime=" + initTime +
                ", density=" + density +
                ", xMax=" + xMax +
                ", xMin=" + xMin +
                ", yMax=" + yMax +
                ", yMin=" + yMin +
                ", ratio=" + ratio +
                ", numOfCellX=" + numOfCellX +
                ", numOfCellY=" + numOfCellY +
                ", sizeOfCellX=" + sizeOfCellX +
                ", sizeOfCellY=" + sizeOfCellY +
                '}';
    }

    public String generateTestInfo() {
        return "初始化用时时间为：" + initTime + "ms\n" +
                "多边形顶点个数为：" + n + "\n" +
                "网格分辨率为：" + numOfCellX + "×" + numOfCellY + "\n" +
                "多边形画像如下：\n" + showEmbellishedNet() + "\n";
    }
}
